package binary_tree

import "fmt"

// 从上到下打印二叉树
// 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行
// 广度优先 BFS

func PrintFromUpToDown(root *TreeNode) {
	if root == nil {
		return
	}
	res := printFromUpToDown(root)
	for i := 0; i < len(res); i++ {
		// 一行的数组
		for _, v := range res[i] {
			fmt.Print(" ")
			fmt.Print(v)
		}
		fmt.Println()
	}
}

// 广度优先遍历

func printFromUpToDown(root *TreeNode) [][]int {
	var res [][]int
	var stack []*TreeNode
	stack = append(stack, root)
	for len(stack) != 0 {
		n := len(stack) // n 代表上一层的节点数量
		var v []int
		for i := 0; i < n; i++ { // 一行一行的打印 区别点就在这里
			node := stack[0]
			stack = stack[1:]
			if node != nil {
				v = append(v, node.val)
				if node.left != nil {
					stack = append(stack, node.left)
				}
				if node.right != nil {
					stack = append(stack, node.right)
				}
			}
		}
		if len(v) > 0 {
			res = append(res, v)
		}
	}
	return res
}

func LevelOrder(root *TreeNode) {
	if root == nil {
		return
	}
	res := levelOrder(root)
	for _, v := range res {
		fmt.Println(v)
	}
}

// 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印
func levelOrder(root *TreeNode) []int {
	var res []int
	var stack []*TreeNode
	stack = append(stack, root) // 存放每次遍历的节点
	for len(stack) != 0 {
		node := stack[0]
		stack = stack[1:]
		if node != nil {
			res = append(res, node.val)
			if node.left != nil {
				stack = append(stack, node.left) // 左节点入栈
			}
			if node.right != nil {
				stack = append(stack, node.right) // 右节点入栈
			}
		}
	}
	return res
}
